
# This is our feature theory
# ipaFeatures are fully specified, diacritics are only partially specified, to
# overwrite whatever they combine with.
from featureMap import ipaFeatures, ipaDiacriticFeatures

# TODO: morpheme boundary feaures, etc.
features = ipaFeatures[ipaFeatures.keys()[0]].keys()

#======================================================================

class Symbol(object):
    """
    Essentially a feature bundle, or wrapper around a feature specification
    dictionary, together with useful methods. Could represent a phoneme, or
    any other structural element that appears in a phonological
    form/representation (e.g., boundary markers, etc.).
    """

    def __init__(self, unicodeStrOrFeatureDict=None, baseFeatureMap=None,
            diacriticFeatureMap=None):
        self.features = {}
        self.baseFeatureMap = baseFeatureMap or ipaFeatures
        self.diacriticFeatureMap = diacriticFeatureMap or ipaDiacriticFeatures
        self.uStr = ''
        self.tipaStr = ''

        # copying symbols
        if isinstance(unicodeStrOrFeatureDict, Symbol):
            self.features = dict(unicodeStrOrFeatureDict.features)
            self.baseFeatureMap = unicodeStrOrFeatureDict.baseFeatureMap
            self.diacriticFeatureMap = unicodeStrOrFeatureDict.diacriticFeatureMap
            self.uStr = unicodeStrOrFeatureDict.uStr
            self.tipaStr = unicodeStrOrFeatureDict.tipaStr
            return

        if type(unicodeStrOrFeatureDict) is dict:
            self.features.update(unicodeStrOrFeatureDict)
            return
        if not unicodeStrOrFeatureDict:
            return

        # it's a nonempty string
        self.uStr = unicodeStrOrFeatureDict
        haveBase = False
        for ch in unicodeStrOrFeatureDict:
            if ch in self.baseFeatureMap:
                if haveBase:
                    raise ValueError('Symbol constructor string must contain '
                                     'only one base phoneme. Found second '
                                     'base phoneme %s' % ch)
                baseFeatures = self.baseFeatureMap[ch]
                if 'tipa' in baseFeatures:
                    self.tipaStr += baseFeatures['tipa']
                self.features.update(baseFeatures)
                haveBase = True
            elif ch in self.diacriticFeatureMap:
                if not haveBase:
                    raise ValueError('Symbol constructor string must contain '
                                     'a base phoneme. Found diacritic without '
                                     'base: %s' % ch)
                diacriticFeatures = self.diacriticFeatureMap[ch]
                tipaLeft, tipaRight = diacriticFeatures['tipa'] 
                self.tipaStr = tipaLeft + self.tipaStr + \
                    tipaRight
                self.features.update(diacriticFeatures)
        if 'tipa' in self.features:
            del self.features['tipa']

    def __str__(self):
        if self.uStr:
            return self.uStr
        return '[%s]' % ', '.join(['%s%s' % (v and '+' or '-', f) for f,v in \
            self.features.iteritems()])

    def __repr__(self):
        return 'Symbol(%s)' % repr(self.uStr or self.features)

    def ascii(self):
        # TODO something better
        return repr(self.uStr)

    def __getitem__(self, key):
        return self.features[key]

    def __setitem__(self, key, value):
        self.features[key] = value

    def __eq__(self, another):
        if hasattr(another, 'features'):
            return self.features == another.features
        return False

    def __ne__(self, another):
        return not (self == another)

    def __hash__(self):
        posFeatures = tuple(sorted([f for f,v in self.features.iteritems() if \
            v]))
        negFeatures = tuple(sorted([f for f,v in self.features.iteritems() if \
            not v]))
        return hash(('SymbolHash', posFeatures, negFeatures))

    def update(self, symbolOrDict):
        if isinstance(symbolOrDict, Symbol):
            self.features.update(symbolOrDict.features)
        else:
            self.features.update(symbolOrDict)
        return self

    def unifies(self, symbolOrDict):
        """
        Tests whether this Symbol's features are consistent with (i.e., are a
        superset of) the features of the given symbol, or with the given feature
        dictionary.
        """
        if isinstance(symbolOrDict, Symbol):
            otherFeatures = symbolOrDict.features
        elif isinstance(symbolOrDict, dict):
            otherFeatures = symbolOrDict
        else:
            raise TypeError('symbolOrDict %r must be a Symbol instance or a '\
                    'feature dictionary.' % symbolOrDict)

        for f, val in otherFeatures.iteritems():
            if (f not in self.features) or (bool(self.features[f]) != bool(val)):
                return False
        return True

#======================================================================

class Form(object):
    """
    A sequence of Symbols.
    """

    def __init__(self, unicodeStrOrSymbolList=None, baseFeatureMap=None,
            diacriticFeatureMap=None):
        self.symbols = []
        self.baseFeatureMap = baseFeatureMap or ipaFeatures
        self.diacriticFeatureMap = diacriticFeatureMap or ipaDiacriticFeatures

        if isinstance(unicodeStrOrSymbolList, list):
            self.symbols = []
            for s in unicodeStrOrSymbolList:
                if s and isinstance(s, Symbol): self.symbols.append(s)

            return

        unicodeStr = unicodeStrOrSymbolList
        if not unicodeStr:
            return

        curSymbolStr = None
        for ch in unicodeStr:
            if ch in self.baseFeatureMap:
                if curSymbolStr:
                    self.symbols.append(Symbol(curSymbolStr, self.baseFeatureMap,
                        self.diacriticFeatureMap))
                curSymbolStr = ch
            elif ch in self.diacriticFeatureMap:
                if not curSymbolStr:
                    raise ValueError('Form constructor string contains '
                                     'diacritic without a base: %s' %ch)
                self.curSymbolStr += ch
            else:
                raise ValueError('Unknown symbol represented by character %r. '
                 'unicodeStr = %r' % (ch, unicodeStr))
        if curSymbolStr:
            self.symbols.append(Symbol(curSymbolStr, self.baseFeatureMap,
                self.diacriticFeatureMap))

    def __str__(self):
        return ''.join([str(s) for s in self.symbols])
    
    def __repr__(self):
        return 'Form(%s)' % (repr(str(self)),)

    def __len__(self):
        return len(self.symbols)

    def __add__(self, another):
        otherForm = isinstance(another, Form) and another or Form(another,
                self.baseFeatureMap, self.diacriticFeatureMap)
        result = Form()
        result.symbols = self.symbols + another.symbols
        return result

    def __getitem__(self, index):
        return self.symbols[index]

    def __setitem__(self, index, value):
        if not isinstance(value, Symbol):
            raise TypeError('value must be an instance of Symbol')
        self.symbols[index] = value

    def __iter__(self):
        return self.symbols.__iter__() 

    def addForm(self, another):
        otherForm = isinstance(another, Form) and another or Form(another,
                self.baseFeatureMap, self.diacriticFeatureMap)
        for sym in otherForm:
            self.appendSymbol(sym)

    def appendSymbol(self, symbol):
        if not isinstance(symbol, Symbol):
            raise TypeError('symbol must be an instance of Symbol.')
        self.symbols.append(symbol)
            
    def __cmp__(self, other):
        if not isinstance(other, Form):
            raise TypeError('no!')
        return cmp(self.symbols, other.symbols)

    def __hash__(self):
        return hash(tuple(self.symbols))

#======================================================================

# A basic default inventory of non-diacritic phonemes (length-1 forms)
# TODO: Use symbols, not length-1 Forms.
defaultInventory = [Symbol(ch) for ch in ipaFeatures]

#======================================================================

nextLangNum = 1

# TODO:
# Correspondence. Language maps input to a Mapping, which specifies output and
# correspondence, which i a set of (inIdx,outIdx) pairs, with None for
# insertion/deletion.
# Then, MultiLanguage, which allows multiple mappings per input
# ProbLanguage, which is a MultiLanguage with probabilities associated to each
# mapping.
class Language(object):
    def __init__(self, dictOrList=None, name=None, inventory=None):
        global nextLangNum

        self.mapping = dictOrList and dict(dictOrList) or {}
        self.name = name or 'Language %04d' % nextLangNum
        nextLangNum += 1
        self.inventory = inventory or defaultInventory

    def __eq__(self, otherLang):
        return self.mapping == otherLang.mapping

    def __neq__(self, otherLang):
        return self.mapping != otherLang.mapping

    def __repr__(self):
        return "Language(%s, %s, %s)" % (self.mapping, self.name, self.inventory)

    def __str__(self):
        pass

    def __getitem__(self, key):
        return self.mapping[key]

    def __setitem__(self, key, value):
        for sym in key:
            pass
        self.mapping[key] = value

#======================================================================
# Some useful functions for generating permutation/combinations

def factorial(x):
    r = 1
    while x:
        r *= x
        x -= 1
    return r

def permutations(L):
    """
    Generator of the permutations of the given list. Will destroy L.
    """
    if len(L) <= 1:
        yield tuple(L)
    else:
        a = (L.pop(0),)
        for p in permutations(L):
            for i in range(len(p)+1):
                yield p[:i] + a + p[i:]

def modcycle(start, mod):
    nYielded = 0
    x = start
    while x < mod:
        yield x
        x += 1
    x = 0
    while x < start:
        yield x
        x += 1

def __permutationSample(L, n):
    """
    Generator of a size-n uniformly random sample of the permutations of L.
    """
    # Slow but unbiased method. Especially slow when n is near len(L).
    #yielded = {}
    #counts = defaultdict(lambda x: defaultdict(int)) # i -> symbol -> count
    #while n:
    #    perm = []
    #    lc = list(L)
    #    i = 0
    #    while lc:
    #        x = random.choice(lc)
    #        perm.append(x)
    #        lc.remove(x)
    #        i += 1
    #    perm = reduce(operator.add, perm)
    #    if perm not in yielded:
    #        yielded[perm] = None
    #        n -= 1
    #        yield perm

    # Fast but possibly biased method? 
    lenL = len(L)
    if lenL <= 1:
        yield tuple(L)
    else:
        samplePercent = float(n) / float(factorial(lenL))
        x = random.choice(L)
        L.remove(x)
        a = (x,)
        for p in permutationSample(L,n):
                #int(round(samplePercent*factorial(lenL-1)))):
            if not n:
                break
            for i in modcycle(random.randint(0,len(p)+1), len(p)+1):
                if not n:
                    break
                n -= 1
                yield p[:i] + a + p[i:]

def permutationSample(L, n):
    """
    Generator of a size-n uniformly random sample of the permutations of L.
    The sample always includes L itself. Does that mean it's not actually
    uniformly random?
    """
    yield tuple(L)
    for x in __permutationSample(L, n-1):
        yield x


def combinationsReplacement(items, n):
    """
    Generates all size-n combinations of elements of items with replacement.
    """
    if n == 1:
        for item in items:
            yield item
    else:
        for i in xrange(len(items)):
            for cc in combinationsReplacement(items, n-1):
                yield items[i] + cc

def combinationsNoReplacement(items, n):
    """
    Generates all size-n combinations of elements of items without replacement.
    """
    if n == 0:
        yield tuple()
    else:
        for i in xrange(len(items)):
            for cc in combinationsNoReplacement(items[:i] + items[i+1:], n-1):
                yield (items[i],) + cc


